Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del 10 luglio 2002

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Usando le notazioni logiche e le operazioni aritmetiche di somma, prodotto ed elevamento a potenza, si trovi una espressione della forma {x | P (x)} che denoti l’insieme dei numeri naturali maggiori di uno che sono potenza di un numero primo (si ricordi che una potenza di un primo è un numero della forma p^{n}, con p primo).

Esercizio 2. Elencare tutti i numeri naturali minori di 20 che appartengono all’insieme

{x | x > 4 → ∀y[(∃k(yk = x) ∧ y è primo ) → y ≤ 5]}.

Esercizio 3. Sia f: N → N la funzione definita nel modo seguente.

f(n) = \{ \begin{matrix}\frac{n}{2} & se n è pari \\ \frac{n}{5} & se n non è pari ed è multiplo di 5 \\ n & se n non è pari e non è multiplo di 5 \end{matrix}

Stabilire se f è iniettiva, surgettiva, biunivoca.

Esercizio 4. Si consideri l’insieme X = {1, 2, …, 1000}.

1. Quanti sono i numeri dell’insieme X che non contegono la cifra 9?

2. Quanti sono i numeri dell’insieme X che sono divisibili per 3 ma non per 4?

3. Quanti sono i numeri dell’insieme X che sono divisibili per almeno uno dei numeri 6 e 9?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza

504x ≡ 551n (mod 91)

ha soluzione, e risolverla per n = 14.

Esercizio 6. Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 0, f_{n+1} = f_{n}^{2} + 1; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 2^{n})

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Usando le notazioni logiche e le operazioni aritmetiche di somma, prodotto ed elevamento a potenza, si trovi una espressione della forma {x | P (x)} che denoti l’insieme dei numeri naturali maggiori di uno che sono potenza di un numero primo (si ricordi che una potenza di un primo è un numero della forma p^{n}, con p primo).

Esercizio 2. Elencare tutti i numeri naturali minori di 50 che appartengono all’insieme

{x | x > 4 → ∀y[(∃k(yk = x) ∧ y è primo ) → y ≥ 7]}

Esercizio 3. Sia f: N → N la funzione definita nel modo seguente.

f(n) = \{ \begin{matrix}\frac{n}{2} & se n è pari \\ \frac{n}{3} & se n non è pari ed è multiplo di 3 \\ n & se n non è pari e non è multiplo di 3 \end{matrix}

Stabilire se f è iniettiva, surgettiva, biunivoca.

Esercizio 4. Si consideri l’insieme X = {1.2…. , 1000}.

1. Quanti sono i numeri dell’insieme X che contengono la cifra 9?

2. Quanti sono i numeri dell’insieme X che sono divisibili per 4 ma non per 3?

3. Quanti sono i numeri dell’insieme X che non sono divisibili né per 4 né per 6?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza

579x ≡ 521n (mod 51)

ha soluzione, e risolverla per n = 15.

Esercizio 6.

Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 1, f_{n+1} = f_{n}^{2} + 1; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 3^{n})

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Usando le notazioni logiche e le operazioni aritmetiche di somma, prodotto ed elevamento a potenza, si trovi una espressione della forma {x | P (x)} che denoti l’insieme dei numeri naturali maggiori di uno che non sono potenza di un numero primo (si ricordi che una potenza di un primo è un numero della forma p^{n}, con p primo).

Esercizio 2. Elencare tutti i numeri naturali minori di 50 che appartengono all’insieme

{x | x > 6 → ∀y[(∃k(yk = x) ∧ y è primo ) → y ≥ 5]}

Esercizio 3. Sia f: N → N la funzione definita nel modo seguente.

f(n) = \{ \begin{matrix}\frac{n}{2} & se n è pari \\ \frac{n}{7} & se n non è pari ed è multiplo di 7 \\ n & se n non è pari e non è multiplo di 7 \end{matrix}

Stabilire se f è iniettiva, surgettiva, biunivoca.

Esercizio 4. Si consideri l’insieme X = {1.2…. , 1000}.

1. Quanti sono i numeri dell’insieme X che non contengono la cifra 5?

2. Quanti sono i numeri dell’insieme X che sono divisibili per 6 ma non per 5?

3. Quanti sono i numeri dell’insieme X che sono divisibili o per 8 o per 12?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza

448x ≡ 552n (mod 77)

ha soluzione, e risolverla per n = 14.

Esercizio 6.

Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 2, f_{n+1} = f_{n}^{2} − 1; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 4^{n})

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Usando le notazioni logiche e le operazioni aritmetiche di somma, prodotto ed elevamento a potenza, si trovi una espressione della forma {x | P (x)} che denoti l’insieme dei numeri naturali maggiori di uno che non sono potenza di un numero primo (si ricordi che una potenza di un primo è un numero della forma p^{n}, con p primo).

Esercizio 2. Elencare tutti i numeri naturali minori di 30 che appartengono all’insieme

{x | x > 5 → ∀y[(∃k(yk = x) ∧ y è primo ) → y ≤ 7]}

Esercizio 3. Sia f: N → N la funzione definita nel modo seguente.

f(n) = \{ \begin{matrix}\frac{n}{2} & se n è pari \\ \frac{n}{1}1 & se n non è pari ed è multiplo di 11 \\ n & se n non è pari e non è multiplo di 11 \end{matrix}

Stabilire se f è iniettiva, surgettiva, biunivoca.

Esercizio 4. Si consideri l’insieme X = {1.2…. , 1000}.

1. Quanti sono i numeri dell’insieme X che non contengono la cifra 5?

2. Quanti sono i numeri dell’insieme X che sono divisibili per 5 ma non per 6?

3. Quanti sono i numeri dell’insieme X che non sono divisibili né per 6 né per 8?

Esercizio 5. Determinare per quali valori dell’intero n la congruenza

462x ≡ 548n (mod 39)

ha soluzione, e risolverla per n = 12.

Esercizio 6.

Sia f_{n} la successione definita per ricorrenza ponendo f_{0} = 1, f_{n+1} = f_{n}^{2} + 1; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 2^{n+1})